We introduce a new method to efficiently approximate the number of infectionsresulting from a given initially-infected node in a network of susceptibleindividuals. Our approach is based on counting the number of possible infectionwalks of various lengths to each other node in the network. We analyticallystudy the properties of our method, in particular demonstrating different formsfor SIS and SIR disease spreading (e.g. under the SIR model our method countsself-avoiding walks). In comparison to existing methods to infer the spreadingefficiency of different nodes in the network (based on degree, k-shelldecomposition analysis and different centrality measures), our method directlyconsiders the spreading process and, as such, is unique in providing estimationof actual numbers of infections. Crucially, in simulating infections on variousreal-world networks with the SIR model, we show that our walks-based methodimproves the inference of effectiveness of nodes over a wide range of infectionrates compared to existing methods. We also analyse the trade-off betweenestimate accuracy and computational cost, showing that the better accuracy herecan still be obtained at a comparable computational cost to other methods.
展开▼
